We study the statistical problem of estimating a rank-one sparse tensor corrupted by additive gaussian noise, a Gaussian additive model also known as sparse tensor PCA. We show that for Bernoulli and Bernoulli-Rademacher distributed signals and \emph{for all} sparsity levels which are sublinear in the dimension of the signal, the sparse tensor PCA model exhibits a phase transition called the \emph{all-or-nothing phenomenon}. This is the property that for some signal-to-noise ratio (SNR) $\mathrm{SNR_c}$ and any fixed $\epsilon> 0$, if the SNR of the model is below $\left(1-\epsilon\right)\mathrm{SNR_c}$, then it is impossible to achieve any arbitrarily small constant correlation with the hidden signal, while if the SNR is above $\left(1+\epsilon \right)\mathrm{SNR_c}$, then it is possible to achieve almost perfect correlation with the hidden signal. The all-or-nothing phenomenon was initially established in the context of sparse linear regression, and over the last year also in the context of sparse 2-tensor (matrix) PCA and Bernoulli group testing. Our results follow from a more general result showing that for any Gaussian additive model with a discrete uniform prior, the all-or-nothing phenomenon follows as a direct outcome of an appropriately defined ``near-orthogonality property of the support of the prior distribution.

We study the statistical problem of estimating a rank-one sparse tensor corrupted by additive gaussian noise, a Gaussian additive model also known as sparse tensor PCA. We show that for Bernoulli and Bernoulli-Rademacher distributed signals and \emph{for all} sparsity levels which are sublinear in the dimension of the signal, the sparse tensor PCA model exhibits a phase transition called the \emph{all-or-nothing phenomenon}. This is the property that for some signal-to-noise ratio (SNR) \mathrm{SNR_c} and any fixed \epsilon 0, if the SNR of the model is below \left(1-\epsilon\right)\mathrm{SNR_c}, then it is impossible to achieve any arbitrarily small constant correlation with the hidden signal, while if the SNR is above \left(1 \epsilon \right)\mathrm{SNR_c}, then it is possible to achieve almost perfect correlation with the hidden signal. The all-or-nothing phenomenon was initially established in the context of sparse linear regression, and over the last year also in the context of sparse 2-tensor (matrix) PCA and Bernoulli group testing. Our results follow from a more general result showing that for any Gaussian additive model with a discrete uniform prior, the all-or-nothing phenomenon follows as a direct outcome of an appropriately defined near-orthogonality" property of the support of the prior distribution.

Gaussian entries, the goal is to recover the k -sparse unit vector x \in \mathbb{R} n . The model captures both sparse PCA (in its Wigner form) and tensor PCA.For the highly sparse regime of k \leq \sqrt{n}, we present a family of algorithms that smoothly interpolates between a simple polynomial-time algorithm and the exponential-time exhaustive search algorithm. For any 1 \leq t \leq k, our algorithms recovers the sparse vector for signal-to-noise ratio \lambda \geq \tilde{\mathcal{O}} (\sqrt{t} \cdot (k/t) {p/2}) in time \tilde{\mathcal{O}}(n {p t}), capturing the state-of-the-art guarantees for the matrix settings (in both the polynomial-time and sub-exponential time regimes).Our results naturally extend to the case of r distinct k -sparse signals with disjoint supports, with guarantees that are independent of the number of spikes. Even in the restricted case of sparse PCA, known algorithms only recover the sparse vectors for \lambda \geq \tilde{\mathcal{O}}(k \cdot r) while our algorithms require \lambda \geq \tilde{\mathcal{O}}(k) .Finally, by analyzing the low-degree likelihood ratio, we complement these algorithmic results with rigorous evidence illustrating the trade-offs between signal-to-noise ratio and running time. This lower bound captures the known lower bounds for both sparse PCA and tensor PCA.